#
# @lc app=leetcode.cn id=199 lang=python3
#
# [199] 二叉树的右视图
#
# https://leetcode-cn.com/problems/binary-tree-right-side-view/description/
#
# algorithms
# Medium (65.42%)
# Likes:    652
# Dislikes: 0
# Total Accepted:    188K
# Total Submissions: 287.5K
# Testcase Example:  '[1,2,3,null,5,null,4]'
#
# 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
# 
# 
# 
# 示例 1:
# 
# 
# 
# 
# 输入: [1,2,3,null,5,null,4]
# 输出: [1,3,4]
# 
# 
# 示例 2:
# 
# 
# 输入: [1,null,3]
# 输出: [1,3]
# 
# 
# 示例 3:
# 
# 
# 输入: []
# 输出: []
# 
# 
# 
# 
# 提示:
# 
# 
# 二叉树的节点个数的范围是 [0,100]
# -100  
# 
# 
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        # 层次遍历；2^0;2^1;2^2是下标了
        # return list of int
        # 第一步，逐层进栈；出完了才是下一层。
        stack = [root]
        result = []
        # case 3
        if root:
            # 逐层入栈
            while stack:
                # not None
                # 只取最后一个结果
                result.append(stack[-1].val)
                # 然后，安排进栈
                temp = []
                for i in stack:
                    if i:
                        # not None
                        if i.left:
                            temp.append(i.left)
                        if i.right:
                            temp.append(i.right)
                # clear stack and update stack
                stack.clear()
                stack = temp
                del temp
        return result
# @lc code=end

